#include "myTree.h"
using namespace std;

TreeNode::TreeNode(char d , TreeNode* lc , TreeNode* rc , NodeTag lt , NodeTag rt )
{
    data=d;
    leftChild =lc;
    rightChild =rc;
    lTag=lt;
    rTag=rt;
}

TreeNode::~TreeNode()
{
    
}

TreeNode::TreeNode(TreeNode *node)//结点的复制
{
    if (node)
    {
        data = node->data;
        leftChild = node->leftChild;
        rightChild = node->rightChild;
        lTag = node->lTag;
        rTag = node->rTag;
    }
}

void TreeNode::printNode()//打印
{
    cout << this->data;
}



MyTree::MyTree() //无参构造，初始化结节点
{
    TreeNode *root = new TreeNode('^', NULL, NULL, Link, Thread);
} 

MyTree::MyTree(const char arr[]) //构造函数
{
    root = new TreeNode('^', NULL, NULL, Link, Link);               // 创建根节点
    root->leftChild = new TreeNode(arr[0], NULL, NULL, Link, Link); // 创建左子节点
    root->rightChild = NULL;
    TreeNode *current = root->leftChild;
    stack<TreeNode *> nodeStack;
    bool createLeft = true; // 标志符，用于指示是否创建左节点

    for (int i = 1; i < strlen(arr); i++)
    {
        if (createLeft)
        {
            if (arr[i] == '@')//@标识空
            {
                current->leftChild = NULL;
                createLeft = false;
            }
            else
            {
                current->leftChild = new TreeNode(arr[i], NULL, NULL, Link, Link);
                nodeStack.push(current);
                current = current->leftChild;
            }
        }//依据先序序列，则一直生成左子树直到为空

        else
        {
            if (arr[i] == '@')
            {
                current->rightChild = NULL;
                if (!nodeStack.empty())
                {
                    current = nodeStack.top();//弹出当前所在结点上一级的结点，构造结点的兄弟的子女
                    nodeStack.pop();
                }
            }
            else
            {
                current->rightChild = new TreeNode(arr[i], NULL, NULL, Link, Link);
                nodeStack.push(current->rightChild);
                if (!nodeStack.empty())
                {
                    current = nodeStack.top();
                    nodeStack.pop();
                }
                createLeft = true;
            }
        }
    }
} 

MyTree::MyTree(const MyTree& othertree) //拷贝函数
{
    root = new TreeNode(othertree.root);//根节点拷贝
    root->leftChild = new TreeNode(othertree.root->leftChild);//左子树拷贝
    if (othertree.root->rightChild != NULL)
    {
        root->rightChild = new TreeNode(othertree.root->rightChild);
    }

    queue<TreeNode *> originalQueue;//原
    queue<TreeNode *> copyQueue;//拷贝

    TreeNode *originalCurrent = new TreeNode(othertree.root->leftChild);
    TreeNode *copyCurrent = root->leftChild;//指示当前位置

    while (!originalQueue.empty() || (originalCurrent->lTag != Thread && originalCurrent->leftChild != NULL) || (originalCurrent->rTag != Thread && originalCurrent->rightChild != NULL)) /*是链接且非空*/
    {
        if (originalCurrent->leftChild != NULL)
        {
            copyCurrent->leftChild = new TreeNode(originalCurrent->leftChild);
        }
        if (originalCurrent->rightChild != NULL)
        {
            copyCurrent->rightChild = new TreeNode(originalCurrent->rightChild);
        }

        if (originalCurrent->lTag != Thread && originalCurrent->leftChild != NULL)
        {
            originalQueue.push(originalCurrent->leftChild);
            copyQueue.push(copyCurrent->leftChild);
        }
        if (originalCurrent->rTag != Thread && originalCurrent->rightChild != NULL)
        {
            originalQueue.push(originalCurrent->rightChild);
            copyQueue.push(copyCurrent->rightChild);
        }
        if (!originalQueue.empty())
        {
            originalCurrent = originalQueue.front();
            copyCurrent = copyQueue.front();
            copyQueue.pop();
            originalQueue.pop();
        }
    }

    if (originalCurrent->leftChild != NULL)
    {
        copyCurrent->leftChild = new TreeNode(originalCurrent->leftChild);
    }
    if (originalCurrent->rightChild != NULL)
    {
        copyCurrent->rightChild = new TreeNode(originalCurrent->rightChild);
    }
} 

MyTree::~MyTree() //析构函数
{
    stack<TreeNode *> nodeStack;
    queue<TreeNode *> nodeQueue;
    TreeNode *current = root->leftChild;

    while (!nodeQueue.empty() || (current->lTag != Thread && current->leftChild != NULL) || (current->rTag != Thread && current->rightChild != NULL))
    {
        if (current->lTag != Thread && current->leftChild != NULL)
        {
            nodeQueue.push(current->leftChild);
            nodeStack.push(current->leftChild);
        }
        if (current->rTag != Thread && current->rightChild != NULL)
        {
            nodeQueue.push(current->rightChild);
            nodeStack.push(current->rightChild);
        }
        if (!nodeQueue.empty())
        {
            current = nodeQueue.front();
            nodeQueue.pop();
        }
    }
    while (!nodeStack.empty())
    {
        TreeNode *nodeToDelete = nodeStack.top();
        nodeStack.pop();
        delete nodeToDelete;
    }
    delete root;
    //通过队列遍历树，将各个节点压入栈中，然后依次弹出依次删除
} 

void MyTree::preOrderTraverse()//前序遍历
{
    stack<TreeNode *> nodeStack;
    TreeNode *current = root->leftChild;
    bool visitedRoot = false;

    cout << root->leftChild->data;

    while (!nodeStack.empty() || ((current->lTag != Thread && current->leftChild != NULL) && !visitedRoot) || (current->rTag != Thread && current->rightChild != NULL))
    {
        if (current->lTag != Thread && !visitedRoot && current->leftChild != NULL)
        {
            nodeStack.push(current);
            current = current->leftChild;
        }
        else if (current->rTag != Thread && current->rightChild != NULL)
        {
            current = current->rightChild;
            visitedRoot = false;
        }
        else if (!nodeStack.empty())
        {
            current = nodeStack.top();
            nodeStack.pop();
            visitedRoot = true;
        }
        if (!visitedRoot)
        {
            cout << current->data;
        }
    }
}

void MyTree::inOrderTraverse()//中序遍历
{
    stack<TreeNode *> nodeStack;
    stack<int> directionStack;
    TreeNode *current = root->leftChild;
    bool backtracking = false;

    nodeStack.push(current);

    while (!nodeStack.empty() || (current->rTag != Thread && current->rightChild != NULL) || (current->leftChild != NULL && current->lTag != Thread && !backtracking))
    {
        while (current->lTag != Thread && !backtracking && current->leftChild != NULL)
        {
            if (current != root->leftChild)
            {
                nodeStack.push(current);
                directionStack.push(1);
            }
            current = current->leftChild;
        }
        cout << current->data;
        if (current->rTag != Thread && current->rightChild != NULL)
        {
            current = current->rightChild;
            backtracking = false;
        }
        else if (!nodeStack.empty())
        {
            current = nodeStack.top();
            backtracking = true;
            nodeStack.pop();
        }
    }
    cout << current->data;//处理最后一个结点
}

void MyTree::postOrderTraverse()//后序遍历
{
    stack<TreeNode *> nodeStack;
    stack<int> directionStack;
    TreeNode *current = root->leftChild;
    int backtracking = 0;

    while (!nodeStack.empty() || backtracking != 2)
    {
        while (current->lTag != Thread && current->leftChild != NULL && backtracking != 2 && backtracking != 1)
        {
            nodeStack.push(current);
            directionStack.push(1);
            current = current->leftChild;
            backtracking = 0;
        }
        if (backtracking == 2)
        {
            cout << current->data;
            if (!nodeStack.empty())
            {
                current = nodeStack.top();
                nodeStack.pop();
                backtracking = directionStack.top();
                directionStack.pop();
            }
        }
        if (current->rTag == Thread || current->rightChild == NULL)
        {
            backtracking = 2;
        }
        else if (current->rTag != Thread && current->rightChild != NULL && backtracking != 2)
        {
            nodeStack.push(current);
            directionStack.push(2);
            current = current->rightChild;
            backtracking = 0;
        }
    }
    if (backtracking == 2)
    {
        cout << current->data;
    }
}

int MyTree::countLeaf() //叶结点
{
     int leafCount = 0;
    queue<TreeNode *> nodeQueue;
    TreeNode *current = root->leftChild;

    while (!nodeQueue.empty() || (current->lTag != Thread && current->leftChild != NULL) || (current->rTag != Thread && current->rightChild != NULL))
    {
        if ((current->lTag == Thread || current->leftChild == NULL) && (current->rightChild == NULL || current->rTag == Thread))
        {
            leafCount++;
        }
        if (current->lTag != Thread && current->leftChild != NULL)
        {
            nodeQueue.push(current->leftChild);
        }
        if (current->rTag != Thread && current->rightChild != NULL)
        {
            nodeQueue.push(current->rightChild);
        }
        if (!nodeQueue.empty())
        {
            current = nodeQueue.front();
            nodeQueue.pop();
        }
    }
    return leafCount + 1;//处理最后一个叶结点
}

int Depth(TreeNode *node)//辅助函数，用于计算某个节点的深度
{
    if ((node->lTag == Thread || node->leftChild == NULL) && (node->rightChild == NULL || node->rTag == Thread))
    {
        return 1;
    }
    if (node->lTag == Thread || node->leftChild == NULL)
    {
        return (Depth(node->rightChild) + 1);
    }
    if (node->rightChild == NULL || node->rTag == Thread)
    {
        return (Depth(node->leftChild) + 1);
    }
    return (max(Depth(node->rightChild), Depth(node->leftChild)) + 1);
}
int MyTree::countHeight() //高度
{
    return Depth(root->leftChild);
}

bool MyTree::isThreadedTree() //判断是否是线索化二叉树
{
    return root->rTag == Thread;
}

bool MyTree::inOrderThreading() //线索化
{
     stack<TreeNode*> nodeStack;
    stack<TreeNode*> tagStack;
    TreeNode* current = root->leftChild; // 当前节点指针，初始化为根节点的左子节点
    TreeNode* predecessor = root;        // 前驱节点指针，初始化为根节点
    int backtrack = 0;
    nodeStack.push(current); // 将根节点的左子节点压入栈中

    // 遍历整个树，线索化节点
    while (!nodeStack.empty() || (current->rTag != Thread && current->rightChild != NULL)) {
        // 找到最左子节点
        while (current->lTag != Thread && !backtrack && current->leftChild != NULL) {
            if (current != root->leftChild) // 如果当前节点不是树的第一个节点
                nodeStack.push(current);
            current = current->leftChild; // 前进到下一个左子节点
        }
        // 线索化左子树
        if (current->leftChild == NULL) {
            current->leftChild = predecessor;
            current->lTag = Thread; // 将左标签标记为线索
        }
        predecessor = current; // 更新前驱节点为当前节点
        tagStack.push(current);
        // 线索化右子树
        if (current->rightChild == NULL) {
            if (!tagStack.empty()) {
                tagStack.top()->rightChild = predecessor;
                tagStack.pop();
            }
            current->rTag = Thread; // 将右标签标记为线索
            tagStack.push(current);
        }
        // 如果有右子节点，遍历右子树
        if (current->rTag != Thread && current->rightChild != NULL) {
            current = current->rightChild;
            backtrack = 0;
        } else if (!nodeStack.empty()) {
            current = nodeStack.top();
            backtrack = 1;
            nodeStack.pop();
        }
    }

    // 线索化最后一个节点的右子树
    current = root->leftChild;
    while (current->rightChild != NULL) {
        current = current->rightChild;
    }
    current->rightChild = root;
    current->rTag = Thread;
    root->rightChild = current;
    root->rTag = Thread;

    return true; // 返回成功
}

TreeNode& MyTree::locateNode(const char& key)
{
     queue<TreeNode*> nodeQueue;
    TreeNode* current = root->leftChild; // 开始节点为根节点的左子节点

    while (!nodeQueue.empty() || (current->lTag != Thread && current->leftChild != NULL) || (current->rTag != Thread && current->rightChild != NULL)) {
        // 查找数据为'key'的节点
        if (current->data == key) {
            return *current;
        }
        if (current->lTag != Thread && current->leftChild != NULL) {
            nodeQueue.push(current->leftChild);
        }
        if (current->rTag != Thread && current->rightChild != NULL) {
            nodeQueue.push(current->rightChild);
        }
        if (!nodeQueue.empty()) {
            current = nodeQueue.front();
            nodeQueue.pop();
        }
    }
    if (current->data == key) {
        return *current;
    } else {
        return *new TreeNode('0', NULL, NULL, Link, Link); // 如果找不到返回一个新的节点
    }
} //结点定位

TreeNode& MyTree::preNode(const TreeNode& target)
{
    string inorderSequence = "";
    stack<TreeNode*> nodeStack;
    TreeNode* current = root->leftChild;
    int backtrack = 0;
    nodeStack.push(current);

    // 中序遍历树，形成字符串
    while (!nodeStack.empty() || (current->rTag != Thread && current->rightChild != NULL)) {
        while (current->lTag != Thread && !backtrack && current->leftChild != NULL) {
            if (current != root->leftChild)
                nodeStack.push(current);
            current = current->leftChild;
        }
        inorderSequence += current->data; // 添加节点数据至字符串
        if (current->rTag != Thread && current->rightChild != NULL) {
            current = current->rightChild;
            backtrack = 0;
        } else if (!nodeStack.empty()) {
            current = nodeStack.top();
            backtrack = 1;
            nodeStack.pop();
        }
    }
    inorderSequence += current->data;

    // 找到数据target的前驱节点并返回
    int index = 0;
    for (; index < inorderSequence.length(); index++) {
        if (inorderSequence[index] == target.data)
            break;
    }
    if (index != 0) {
        return locateNode(inorderSequence[index - 1]);
    } else {
        return *root->rightChild;
    }
}//获取前驱结点
TreeNode& MyTree::nextNode(const TreeNode& target)//获取后继结点
{
     string inorderSequence = "";
    stack<TreeNode*> nodeStack;
    TreeNode* current = root->leftChild;
    int backtrack = 0;
    nodeStack.push(current);

    // 类似前驱节点的方法，遍历并得到字符串
    while (!nodeStack.empty() || (current->rTag != Thread && current->rightChild != NULL)) {
        while (current->lTag != Thread && !backtrack && current->leftChild != NULL) {
            if (current != root->leftChild)
                nodeStack.push(current);
            current = current->leftChild;
        }
        inorderSequence += current->data;
        if (current->rTag != Thread && current->rightChild != NULL) {
            current = current->rightChild;
            backtrack = 0;
        } else if (!nodeStack.empty()) {
            current = nodeStack.top();
            backtrack = 1;
            nodeStack.pop();
        }
    }
    inorderSequence += current->data;

    // 查找后继节点
    int index = 0;
    for (; index < inorderSequence.length(); index++) 
    {
        if (inorderSequence[index] == target.data)
            break;
    }
    if (index != inorderSequence.length()) 
    {
        return locateNode(inorderSequence[index + 1]);
    } 
    else
    {
        return locateNode(inorderSequence[0]);
    }
}
class com
{
public:
    // 比较器，用于排序TreeNode指针
    bool operator()(TreeNode *f, TreeNode *e) const
    {
        return f->data < e->data;
    }
};

HuffmanTree::HuffmanTree(const int &n, const int arr[])
{
    num = n;                                          // 节点数量
    root = new TreeNode('^', NULL, NULL, Link, Link); // 根节点初始化
    int pos[10000];
    multiset<TreeNode *, com> s; // 设置排序容器，使用比较器

    // 插入初始节点到集合中
    for (int i = 0; i < n; i++)
    {
        s.insert(new TreeNode(arr[i], NULL, NULL, Link, Link));
    }
    // 不断合并最小的两个节点形成霍夫曼树

    while (s.size() > 2)
    {
        TreeNode *t1 = *s.begin(); // 取出第一个最小的节点
        s.erase(s.begin());
        TreeNode *t2 = *s.begin(); // 取出第二个最小的节点
        s.erase(s.begin());
        s.insert(new TreeNode((t1->data + t2->data), t1, t2, Link, Link)); 
        //作业要求左边放较小的值，右边放较大的值
    }
    
    // 设置树的根节点的左右子节点
    root->leftChild = *s.begin();
    s.erase(s.begin());
    root->rightChild= *s.begin();
}

HuffmanTree:: ~HuffmanTree()
{
     queue<TreeNode *> s;
    s.push(root); // 将根节点压入队列中
    stack<TreeNode *> del;
    del.push(root); // 将根节点压入删除堆栈
    TreeNode *fron = root;

    // 通过队列遍历所有节点并推入删除堆栈
    while (!s.empty())
    {
        if (fron->leftChild != NULL)
        {
            del.push(fron->leftChild);
            s.push(fron->leftChild);
        }
        if (fron->rightChild != NULL)
        {
            del.push(fron->rightChild);
            s.push(fron->rightChild);
        }
        if (!s.empty())
        {
            if (s.front() == root)
                s.pop(); // 根节点跳过
            fron = s.front();
            s.pop();
        }
    }

    // 删除所有节点
    while (!del.empty())
    {
        delete del.top();
        del.pop();
    }
}

void HuffmanTree::printHuffmanCodes()
{
    TreeNode *fron = root; // 从根节点开始遍历
    queue<TreeNode *> s;   // 节点队列
    queue<string> d;       // 编码队列
    string str;
    string test = "";

    string arr[10000];
    while (!s.empty() || !(fron->rightChild == NULL && fron->leftChild == NULL))
    {
        if (fron->rightChild == NULL && fron->leftChild == NULL)
        {
            // 打印叶子节点和对应的编码
            cout << int(fron->data) << ":" << d.front() << endl;
            d.pop();
            s.pop();
        }
        
        if (fron->rightChild != NULL)
        {
            string te = "";
            if (!d.empty())
            {
                te = d.front();
                test = d.front();
                d.pop();
                s.pop();
            }
            d.push(te + "1"); // 右子节点编码为'1'
            s.push(fron->rightChild);
        }
        if (fron->leftChild != NULL)
        {
            d.push(test + "0"); // 左子节点编码为'0'
            s.push(fron->leftChild);
        }
        if (!s.empty())
        {
            fron = s.front();
        }
    }
}